package base_Suanfa.dongtaiguihua;

import java.util.Arrays;

//对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
//
//给定字符串A以及它的长度n，请返回最长回文子串的长度。 "abc1234321ab",12  长度为7
public class max_huiwenchuan {
    public static void main(String[] args) {
        //String s="abc1234321ab";
        String s="ascqs";
        char a[]= s.toCharArray();
        boolean b[][]=new boolean[s.length()][s.length()];
        for(int i=0;i<s.length();i++){
            b[i][i]=true;     //自己和自己是回文串
        }
        int max=1;
        for(int j=1;j<s.length();j++){
            for(int i=j-1;i>=0;i--){
                if(j-i==1){
                    b[i][j]=(a[i]==a[j]);
                    if(b[i][j]==true&&max<j-i+1)
                        max=j-i+1;
                }
                else {
                        if (b[i + 1][j - 1] && a[j] == a[i]) {
                            b[i][j] = true;
                            if (max < j - i + 1)
                                max = j - i + 1;
                        } else
                            b[i][j] = false;

                }
            }
        }
        System.out.println(max);
    }
}
